λ¬Έμ
nκ°μ μμ΄ μλ μ μλ€μ΄ μμ΅λλ€. μ΄ μ μλ€μ μμλ₯Ό λ°κΎΈμ§ μκ³ μ μ ν λνκ±°λ λΉΌμ νκ² λλ²λ₯Ό λ§λ€λ €κ³ ν©λλ€. μλ₯Ό λ€μ΄ [1, 1, 1, 1, 1]λ‘ μ«μ 3μ λ§λ€λ €λ©΄ λ€μ λ€μ― λ°©λ²μ μΈ μ μμ΅λλ€.
-1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3
μ¬μ©ν μ μλ μ«μκ° λ΄κΈ΄ λ°°μ΄ numbers, νκ² λλ² targetμ΄ λ§€κ°λ³μλ‘ μ£Όμ΄μ§ λ μ«μλ₯Ό μ μ ν λνκ³ λΉΌμ νκ² λλ²λ₯Ό λ§λλ λ°©λ²μ μλ₯Ό return νλλ‘ solution ν¨μλ₯Ό μμ±ν΄μ£ΌμΈμ.
μ νμ¬ν
- μ£Όμ΄μ§λ μ«μμ κ°μλ 2κ° μ΄μ 20κ° μ΄νμ λλ€.
- κ° μ«μλ 1 μ΄μ 50 μ΄νμΈ μμ°μμ λλ€.
- νκ² λλ²λ 1 μ΄μ 1000 μ΄νμΈ μμ°μμ λλ€.
μ μΆλ ₯ μ
| numbers | target | return |
|---|---|---|
| [1, 1, 1, 1, 1] | 3 | 5 |
| [4, 1, 2, 1] | 4 | 2 |
π Logic
private void dfs(int[] numbers, int idx, int target, int sum) {
if (idx + 1 == numbers.length) {
if (sum == target) answer++;
return;
}
dfs(numbers, idx + 1, target, sum + numbers[idx + 1]);
dfs(numbers, idx + 1, target, sum - numbers[idx + 1]);
}
- μ¬κ·μ μΈ DFSλ₯Ό μ΄μ©ν΄ λ€μ numberλ₯Ό λνκ±°λ λΉΌλ©΄μ 맨 λ§μ§λ§ κ°μ΄ νκ² λλ²μ κ°μ κ²½μ° answerλ₯Ό μ¦κ°νλ€.
- 첫 λ²μ§Έ μ«μκ° μμμΈ κ²½μ°μ μμμΈ κ²½μ° λ κ°μ§μ λν΄ dfsλ₯Ό νΈμΆνλ€.
π CODE
μ½λ 보기/μ κΈ°π«
import java.util.*;
class Solution {
static int answer = 0;
public int solution(int[] numbers, int target) {
dfs(numbers, 0, target, numbers[0]);
return answer;
}
private void dfs(int[] numbers, int idx, int target, int sum) {
if (idx + 1 == numbers.length) {
if (sum == target) answer++;
return;
}
dfs(numbers, idx + 1, target, sum + numbers[idx + 1]);
dfs(numbers, idx + 1, target, sum - numbers[idx + 1]);
}
}
βοΈ Review
- μ²μμλ νΈλ¦¬λ₯Ό λ§λ€μ΄μ 맨 λ§μ§λ§ 리ν λ Έλκ° νκ² λλ²λ κ°μ κ²½μ°μ μλ₯Ό 체ν¬ν΄μΌνλ μκ°νλ€.
- μ΄μ μ DFS λ¬Έμ λ₯Ό ν λ λκ° μ¬κ· νΈμΆμ μ΄μ©ν DFSλ‘ λΉμ·ν λ¬Έμ λ₯Ό νμλ κ²μ΄ μκ°λ ꡬνν΄λ³΄λ μ λ΅μ΄μλ€.
- μΈλ°μμ΄ νΈλ¦¬λ₯Ό ꡬνν λ» νλ€.
π μΆμ²
Programmers : https://programmers.co.kr/learn/courses/30/lessons/43165